548. Split Array with Equal Sum
Medium

Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions:

  • 0 < i, i + 1 < j, j + 1 < k < n - 1
  • The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.
A subarray (l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.

 

Example 1:

Input: nums = [1,2,1,2,1,2,1]
Output: true
Explanation:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Example 2:

Input: nums = [1,2,1,2,1,2,1,2]
Output: false

 

Constraints:

  • n == nums.length
  • 1 <= n <= 2000
  • -106 <= nums[i] <= 106
Accepted
17.8K
Submissions
36.4K
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.50 (12 votes)

Premium

Solution


Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

Before we start looking at any of the approaches for solving this problem, firstly we need to look at the limits imposed on ii, jj and kk by the given set of constraints. The figure below shows the maximum and minimum values that ii, jj and kk can assume.

Split_Array

Thus, the limits based on the length of the array nn can now be rewritten as:

1 ≤ i ≤ n-6

i+2 ≤ j ≤ n-4

j+2 ≤ k ≤ n-2

Having discussed the limits imposed on the cuts ii, jj, kk that we will apply on the given array numsnums, let's look at the first solution that comes to our mind.

We simply traverse over all the elements of the array. We consider all the possible subarrays taking care of the constraints imposed on the cuts, and check if any such cuts exist which satisfy the given equal sum quadruples criteria.

Complexity Analysis

  • Time complexity : O(n4)O(n^4). Four for loops inside each other each with a worst case run of length nn.
  • Space complexity : O(1)O(1). Constant Space required.

Approach #2 Cumulative Sum [Time Limit Exceeded]

Algorithm

In the brute force approach, we traversed over the subarrays for every triplet of cuts considered. Rather than doing this, we can save some calculation effort if we make use of a cumulative sum array sumsum, where sum[i]sum[i] stores the cumulative sum of the array numsnums upto the ithi^{th} element. Thus, now in order to find the sum(subarray(i:j))sum\big(subarray(i:j)\big), we can simply use sum[j]sum[i]sum[j]-sum[i]. Rest of the process remains the same.

Complexity Analysis

  • Time complexity : O(n3)O(n^3). Three for loops are there, one within the other.

  • Space complexity : O(n)O(n). sumsum array of size nn is used for storing cumulative sum.


Approach #3 Slightly Better Approach [Time Limit Exceeded]

Algorithm

We can improve the previous implementation to some extent if we stop checking for further quadruples if the first and second parts formed till now don't have equal sums. This idea is used in the current implementation.

Complexity Analysis

  • Time complexity : O(n3)O(n^3). Three loops are there.

  • Space complexity : O(n)O(n). sumsum array of size nn is used for storing the cumulative sum.


Approach #4 Using HashMap [Time limit Exceeded]

Algorithm

In this approach, we create a data structure called mapmap which is simply a HashMap, with data arranged in the format:

{csum(i):[i1,i2,i3,....]}\big\{csum(i):[i_1,i_2,i_3,....]\big\}, here csum(i)csum(i) represents the cumulative sum in the given array numsnums upto the ithi^{th} index and its corresponding value represents indices upto which cumulative sum=csum(i).

Once we create this mapmap, the solutions gets simplified a lot. Consider only the first two cuts formed by ii and jj. Then, the cumulative sum upto the (j1)th(j-1)^{th} index will be given by: csum(j1)=sum(part1)+nums[i]+sum(part2)csum(j-1)=sum(part1) + nums[i] + sum(part2). Now, if we want the first two parts to have the same sum, the same cumulative sum can be rewritten as:

csum(j1)=csum(i1)+nums[i]+csum(i1)=2csum(i1)+nums[i]csum'(j-1) = csum(i-1) + nums[i] + csum(i-1) = 2csum(i-1) + nums[i].

Thus, we traverse over the given array, changing the value of the index ii forming the first cut, and look if the mapmap formed initially contains a cumulative sum equal to csum(j1)csum'(j-1). If mapmap contains such a cumulative sum, we consider every possible index jj satisfying the given constraints and look for the equalities of the first cumulative sum with the third and the fourth parts.

Following the similar lines as the discussion above, the cumulative sum upto the third cut by kthk^{th} index is given by

csum(k1)=sum(part1)+nums[i]+sum(part2)+nums[j]+sum(part3)csum(k-1) = sum(part1) + nums[i] + sum(part2) + nums[j] + sum(part3).

For equality of sum, the condition becomes:

csum(k1)=3csum(i1)+nums[i]+nums[j]csum'(k-1) = 3*csum(i-1) + nums[i] + nums[j].

Similarly, the cumulative sum upto the last index becomes:

csum(end)=sum(part1)+nums[i]+sum(part2)+nums[j]+sum(part3)+nums[k]+sum(part4)csum(end) = sum(part1) + nums[i] + sum(part2) + nums[j] + sum(part3) + nums[k] + sum(part4).

Again, for equality, the condition becomes:

csum(end)=4csum(i1)+nums[i]+nums[j]+nums[k]csum'(end) = 4*csum(i-1) + nums[i] + nums[j] + nums[k].

For every cut chosen, we look if the required cumulative sum exists in mapmap. Thus, we need not calculate sums again and again or traverse over the array for all the triplets (i,j,k)(i, j, k) possible. Rather, now, we directly know, what cumulative sum to look for in the mapmap, which reduces a lot of computations.

Complexity Analysis

  • Time complexity : O(n3)O(n^3). Three nested loops are there and every loop runs nn times in the worst case. Consider the worstcase [0,0,0....,1,1,1,1,1,1,1].

  • Space complexity : O(n)O(n). HashMap size can go upto nn.


Approach #5 Using Cumulative Sum and HashSet [Accepted]

Algorithm

In this approach, firstly we form a cumulative sum array sumsum, where sum[i]sum[i] stores the cumulative sum of the array numsnums upto the ithi^{th} index. Then, we start by traversing over the possible positions for the middle cut formed by jj. For every jj, firstly, we find all the left cut's positions, ii, that lead to equalizing the sum of the first and the second part (i.e. sum[i1]=sum[j1]sum[i]sum[i-1] = sum [j-1] - sum[i]) and store such sums in the setset (a new HashSet is formed for every jj chosen). Thus, the presence of a sum in setset implies that such a sum is possible for having equal sum of the first and second part for the current position of the middle cut(jj).

Then, we go for the right cut and find the position of the right cut that leads to equal sum of the third and the fourth part (sum[n1]sum[k]=sum[k1]sum[j]sum[n-1]-sum[k]=sum[k-1] - sum[j]), for the same middle cut as chosen earlier. We also, look if the same sum exists in the setset. If so, such a triplet (i,j,k)(i, j, k) exists which satisfies the required criteria, otherwise not.

Look at the animation below for a visual representation of the process:

Current
1 / 10

Complexity Analysis

  • Time complexity : O(n2)O(n^2). One outer loop and two inner loops are used.

  • Space complexity : O(n)O(n). HashSet size can go upto nn.

Report Article Issue

Comments: 25
ningquan's avatar
Read More

Why I feel this should be a hard problem.

86
Reply
Share
Report
__thalaiva__'s avatar
Read More

Leetcode, please mark this question as hard before some half baked "smart" interviewer asks this in an interview to solve in 15 minutes.

52
Reply
Share
Report
Three_Thousand_world's avatar
Read More

WHY

52
Reply
Share
Report
__thalaiva__'s avatar
Read More

This should be marked as hard. Leetcode, pleaaaseeeeee curate the questions and tag appropriately.

9
Reply
Share
Report
MaidaWu's avatar
Read More

This solution is so smart. It just split two nested for loop and use the middle j to make sure that left for loop won't disrupt with the right half for loop. Two nested for loop is O(n^4) but once you split them, it's O(n^2)+O(n^2). I've solved hundreds of leetcode, but seldom did I meet such kind of solution using split nested for loop skills.

5
Reply
Share
Report
lee215's avatar
Read More

Solution O(N^2)

def splitArray(self, nums):
        n = len(nums)
        s = [0] * (n + 1)
        for i in range(n): s[i + 1] = s[i] + nums[i]
        def check(l, r):
            return set(s[m] - s[l] for m in range(l + 1, r + 1) if s[m] - s[l] == s[r + 1] - s[m + 1])
        return any(check(0, j - 1) & check(j + 1, n - 1) for j in range(n))

10
Show 1 reply
Reply
Share
Report
the_rainy_day's avatar
Read More

I find it's useful to write down the relations between prefix sum and target numbers to understand approach 5:

# [0...i-1], i, [i+1...j-1], j, [j+1...k-1], k, [k+1...n-1]

# [0...i-1] = s
# [0...j-1] = 2s + nums[i]
# [0...k-1] = 3s + nums[i] + nums[j]
# [0...n-1] = 4s + nums[i] + nums[j] + nums[k]

2
Reply
Share
Report
aruballos's avatar
Read More

I believe the animation might be wrong? See the screenshot below:
0_1493002922513_Capture.PNG

sum[k-1] - sum[j] = 28 - 20 = 8
sum[n-1] - sum[k] = 36 - 30 = 6

8 != 6

1
Reply
Share
Report
vinod23's avatar
Read More

@aruballos Thanks for pointing it out. I have updated the animation. Please take a look.

0
Reply
Share
Report
xhd2015's avatar
Read More

No, I think time complexity is O(n^2log(n)) , because set.add() will cost log(n)

0
Show 2 replies
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium